#include <iostream>
using namespace std;

#define int long long  // 处理大数

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, a, b;
        cin >> n >> a >> b;

        if (a == 1) {
            // a=1时，元素为1 + s*b，需满足n=1或n mod
            // b=1或b=1（b=1时所有n≥1都满足）
            if (n == 1 || n % b == 1 || b == 1) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
            continue;
        }

        // a>1时，检查是否存在a^i使得a^i mod b == n mod b且a^i <=n
        int target_mod = n % b;
        bool found = false;
        for (int i = 1; i <= n; i *= a) {  // 枚举a^0=1, a^1=a, a^2=a²...
            if (i % b == target_mod) {
                found = true;
                break;
            }
        }

        cout << (found ? "Yes" : "No") << '\n';
    }

    return 0;
}